Computer systems frequently include graphics displays such as a display screen or graphic printer capable of displaying curves and alphanumeric characters. FIG. 1 illustrates a curve 2 and a series of alphanumeric characters 3 in the form of a graph that may be displayed on a typical computer display screen or graphic printer.
Graphic images are shown on the display screen or printer as a series of small dots. A pixel represents the smallest element or dot on the display screen or printer that can be addressed. The display screen or printed page is made up of many scan lines arranged in one dimension, typically the horizontal dimension, with each scan line being one pixel high. Each horizontal scan line is comprised of a series of pixels. As an example, a typical laser printer may have a resolution of 300 dots per inch. This means that the printed page is made up of 300 horizontal scan lines per inch, and each horizontal scan line is made up of 300 pixels per inch. A curve or alphanumeric character is displayed by the display screen or the printer using a group of pixels that approximates the curve and character.
A graphics display computer system generally includes a memory for storing a digital representation of the curve or character to be displayed. In prior art computer system, the digital values represent each pixel on the display screen or printed page. This approach to graphics display would require an extremely large memory to represent digital values for each pixel of a graphics display. Such a system is too slow when initially generating digital values which represent a curve, and is also too slow when manipulating the curve, such as when the curve is rotated or relocated on the display screen. Similarly, prior art computer systems represent graphic alphanumeric characters in memory as a bit-map where each bit in the bit-map corresponds to a pixel on the display screen. The curves of the individual alphanumeric characters are defined by the bit-map data for each alphanumeric character. This requires large amounts of memory to store the bit-map data and made it difficult to manipulate the alphanumeric characters, such as changing font type or font size. Because of these problems, many computer graphics systems utilize the Bezier spline method of modeling curves. This included a method of modeling alphanumeric characters as a series of lines and Bezier splines, as is common in TrueType.TM. character fonts.
A Bezier spline, often referred to as a Bezier curve, is a mathematical construct for curves and curved surfaces. A commonly used Bezier curve for two-dimensional graphics systems is a quadratic Bezier curve 4 illustrated in FIG. 2. The quadratic Bezier curve 4 requires three control points, 5, 6, and 7, to define the curve 4. Once the three control points are specified, the Bezier curve 4 is defined. However, as is well known to those skilled in the art, higher order Bezier curves may be used to create highly complex curves in two, three or higher dimensions. Thus, complex Bezier curves may be represented by just a few points.
While Bezier curves permit a curve to be defined by a small set of data points, when the Bezier curve itself is to be displayed on the display screen, the data values for each pixel used to trace out the curve must be specified. Since determining each and every data point on a curve is a slow, computationally inefficient process, it has been found highly beneficial to approximate the Bezier curve. An advantage of doing this is that the Bezier curve can be approximated very closely by a finite set of line segments. The number of line segments required to suitably approximate the Bezier curve depends on several factors including the rate of curvature of the Bezier curve and the resolution of the display screen or printer. Approximating a curve by a finite set of line segments is called "rendering the curve."
The above discussion is equally applicable to other graphics devices as well as display screens and printers although some parameters may vary. The pixel size on a typical laser printer, for example, is different from the pixel size on a typical display screen. However, the same problems encountered in rendering a Bezier curve on a display screen are present when rendering a curve on a laser printer or any other type of graphics display.
The typical method of rendering a Bezier curve requires a determination of which pixels should be turned on and which pixels should be turned off to visually represent a curved line. Note that the terms turning on and off simply refer to the fact that the pixels have two opposite binary logic states. It is obvious that a pixel that is turned on may create a lighted area on a display screen or a darkened area on the printed page, depending on the particular display mode (e.g., reverse video). For purposes of this application, turning a pixel on refers to the process of creating a visible dot on the display screen or printed page at the position of the pixel. Similarly, turning a pixel off refers to the process of leaving the particular pixel invisible on the display screen or printed page.
To render a Bezier curve in the prior art, the curve is first broken into a series of line segments each with a length dependent on such factors as the rate of curvature and the resolution of the graphic display. Systems of the prior art must then determine which pixels should be turned on to approximate the line segments that are used to approximate the Bezier curve. Line rendering procedures generally use the well-known Bresenham algorithm or some variant thereof. This technique generates line segments of variable length to approximate the Bezier curve. A portion of the Bezier curve with a slow rate of curvature can be approximated by longer line segments than a portion of the Bezier curve with a high rate of curvature. However, rendering line segments of variable length can be a slow tedious process that requires many computations.
Therefore, it can be appreciated that there is a significant need for a system and method for rendering Bezier curves without the need for a long computational process.